#include "sorting_algo.h"

void SORTING::selectionSort(std::vector<int> &nums) {
    // 开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾
    std::cout << "选择排序" << std::endl;
    int n = nums.size();
    // 外重循环：未排序区间为[i,n-1]
    for (int i = 0;i < n - 1;i++) {
        // 内层循环，找到未排序区间内的最小元素
        // k用来记录未排序区间内的最小元素的索引
        int k = i;
        for (int j = i + 1;j < n;j++) {
            if (nums[j] < nums[k]) {
                k = j;
            }

        }
        // 将内层循环找到的最小元素与未排序区间的首个元素交换，即交换nums[i]和nums[k]
        mySwap(nums,i,k);
    }
    return;
}

void SORTING::bubbleSort(std::vector<int> &nums) {
    std::cout << "冒泡排序" << std::endl;
    // 从数组最左端开始向右遍历，依次比较相邻元素大小，
    // 如果“左元素>右元素”，就交换他俩，遍历完成后，最大的元素会被移动到数组的最右端
    // 外循环，未排序区间为[0,i]
    for (int i = nums.size() - 1;i > 0;i--) {
        // 内循环，将未排序区间[0,i]中的最大元素交换至该区间的最右端
        for (int j = 0;j < i;j++) {
            if(nums[j] > nums[j + 1]) {
                mySwap(nums,j,j+1);
            }
        }
    }
    return;
}

void SORTING::bubbleSortWithFlag(std::vector<int> &nums) {
    std::cout << "冒泡排序(标志优化)" << std::endl;
    // 从数组最左端开始向右遍历，依次比较相邻元素大小，
    // 如果“左元素>右元素”，就交换他俩，遍历完成后，最大的元素会被移动到数组的最右端
    // 如果内层循环一轮都未发生元素交换，说明数组排序完成，可以直接退出循环
    // 外循环，未排序区间为[0,i]
    for (int i = nums.size() - 1;i > 0;i--) {
        bool flag = false; // 每一次外循环，初始化一次标志位
        // 内循环，将未排序区间[0,i]中的最大元素交换至该区间的最右端
        for (int j = 0;j < i;j++) {
            if(nums[j] > nums[j + 1]) {
                mySwap(nums,j,j+1);
                flag = true; // 记录交换元素
            }
        }
        if (!flag) {
            break;  // 此轮冒泡未交换任何元素，直接跳出
        }
    }
    return;
}

void SORTING::insertionSort(std::vector<int> &nums) {
    std::cout << "插入排序" << std::endl;
    // 在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该基准元素插入到正确位置
    // 外循环：已排序元素数量为1，2，...，n，已排序区间为[0,j),逐渐向右扩展
    for (int i = 1;i < nums.size();i++) {
        int base = nums[i];
        int j = i - 1;
        // 内循环:将base插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 将nums[j]向右移动一位
            j--;
        }
        nums[j + 1] = base; //将base赋值到正确位置
    }
}

int SORTING::partition(std::vector<int> &nums,int left,int right) {
    // 将nums[left]作为哨兵
    int i = left;
    int j = right;
    while (i < j) { 
        // 从右向左找首个小于基准数的元素
        while (i < j && nums[j] >= nums[left]) {
            j--;
        }
        // 从左向右找首个大于基准数的元素
        while (i < j && nums[i] <= nums[left]) {
            i++;
        }
        // 交换两个元素
        mySwap(nums,i,j);
    }
    // i和j相遇时，跳出上面的循环，相等处就是两子数组的分界线
    // 将基准数交换至两子数组的分界线
    mySwap(nums,i,left);
    // 返回基准数的索引
    return i;
}

int SORTING::partionWithMed(std::vector<int> &nums,int left,int right) {
    //找到数组最左，中间，最右三个元素的中位数
    int mid = left + (right - left) / 2;
    int med = medianThree(nums,left,mid,right);
    // 交换最左元素和中位数元素
    mySwap(nums,left,med);
    int i = left;
    int j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j--;
        }
        while (i < j && nums[i] <= nums[left]) {
            i++;
        }
        mySwap(nums,i,j);
    }
    mySwap(nums,i,left);
    return i;

}

void SORTING::quickSort(std::vector<int> &nums,int left,int right) {
    // 子数组长度为1时终止递归
    if (left >= right) {
        return;
    }
    // 哨兵划分
    int pivot = partition(nums,left,right);
    // 递归划分左右数组
    quickSort(nums,left,pivot - 1);
    quickSort(nums,pivot + 1,right);
}

void SORTING::quickSortTail(std::vector<int> &nums,int left,int right) {
    // 子数组长度为1时终止递归
    while (left < right)
    {
        // 哨兵划分操作
        int pivot = partition(nums,left,right);
        // 对两个子数组中较短的那个执行快排
        if (pivot - left < right - pivot) {
            quickSortTail(nums,left,pivot - 1);  // 递归排序左子数组
            left = pivot + 1;                    // 剩余未排序区间为[pivot + 1,right]
        }
        else {
            quickSortTail(nums,pivot + 1,right);  // 递归排序左子数组
            right = pivot - 1;                    // 剩余未排序区间为[left,pivot - 1]
        }
    }
    
}



int SORTING::medianThree(std::vector<int> &nums,int left,int mid,int right) {
    // 使用异或运算
    // 异或规则为:相同为假，不同为真： 0^0 = 1^1 = 0,0^1 = 1^0 = 1
    if((nums[left] < nums[mid]) ^ (nums[left] < nums[right])) {
        return left;
    }
    else if((nums[mid] < nums[left]) ^ (nums[mid] < nums[right])) {
        return right;
    }
    else {
        return right;
    }
}

bool SORTING::mySwap(std::vector<int> &nums,int i,int j) {
    if (i < 0 || i > nums.size() - 1 || j < 0 || i > nums.size() - 1) {
        std::cout << "元素索引超出数组范围" << std::endl;
        return false;
    }
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
    return true;
}

void SORTING::merge(std::vector<int> &nums,int left,int mid,int right) {
    // 左子数组区间[left,mid],右子数组区间[mid+1,right]
    // 创建一个临时数组用于存放合并后的结果
    std::vector<int> temp(right - left + 1,0);
    // 初始化左子数组、右子数组和临时数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // 当左右子数组都还有元素时，按元素比较，并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if ( nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        }
        else {
            temp[k++] = nums[j++];
        }
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    // 将临时数组temp中的元素复制回原数组nums对应的区间
    for (k = 0;k < temp.size();k++) {
        nums[left + k] = temp[k];
    }
}

void SORTING::mergeSort(std::vector<int> &nums,int left,int right) {
    // 递归终止条件：数组左边界越过右边界
    if (left >= right) {
        return;
    }
    // 划分左右数组
    int mid = left + (right - left) / 2;
    // 递归左子数组
    mergeSort(nums,left,mid);
    // 递归右子数组
    mergeSort(nums,mid+1,right);
    // 合并左右子数组
    merge(nums,left,mid,right);
}

void SORTING::siftDown(std::vector<int> &nums,int n,int i) {
    while (true) {
        // 判断节点i,左子节点l,右子节点r中值最大的节点，记为ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma]) {
            ma = l;
        }
        if (r < n && nums[r] > nums[ma]) {
            ma = r;
        }
        // 若节点i最大或索引l,r越界，则无需继续堆化，跳出
        if (ma == i) {
            break;
        }
        // 交换两节点的值
        mySwap(nums,i,ma);
        // 循环向下堆化
        i = ma;
    }
}

void SORTING::heapSort(std::vector<int> &nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.size() / 2 - 1;i >= 0;--i) {
        siftDown(nums,nums.size(),i);
    }
    // 从堆中提取出最大元素，循环n-1轮
    for (int i = nums.size() - 1;i > 0;--i) {
        // 交换根节点与最右叶节点（即交换首元素与尾元素）
        mySwap(nums,0,i);
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums,i,0);
    }
}

void SORTING::bucketSort(std::vector<float> &nums) {
    // 初始化k = n / 2个桶，预期向每个桶分配2个元素
    int k = nums.size() / 2;
    std::vector<std::vector<float>> buckets(k);
    // 将数组元素分配到各个桶中
    for (float num:nums) {
        // 输入数据范围[0,1),使用num * k映射到索引范围[0,k-1]
        int i = num * k;
        buckets[i].push_back(num);
    }
    // 对各个桶执行排序
    for (std::vector<float> &bucket : buckets) {
        sort(bucket.begin(),bucket.end());
    }
    // 遍历桶合并结果
    int i = 0;
    for (std::vector<float> &bucket : buckets) {
        for (float num :nums) {
            nums[i++] = num;
        }
    }
}

void SORTING::countingSortNaive(std::vector<int> &nums) {
    std::cout << "计数排序,简单实现"  << std::endl;
    // 1、统计数组最大元素m
    int m = 0;
    for (int num:nums) {
        m = max(m,num);
    }
    // 2、统计各数字出现的次数
    // counter[num]代表num的出现次数
    std::vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }

    // 3、遍历counter，将各元素填入原数组nums
    int i = 0;
    for (int num = 0;num < m + 1;num++) {
        for (int j = 0;j < counter[num];j++,i++) {
            nums[i] = num;
        }
    }
 }


void SORTING::countingSort(std::vector<int> &nums) {
    std::cout << "计数排序,完整实现"  << std::endl;
    // 1、统计数组最大元素m
    int m = 0;
    for (int num:nums) {
        m = max(m,num);
    }
    // 2、统计各数字出现的次数
    // counter[num]代表num的出现次数
    std::vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3、求counter的前缀和，将"出现次数"转换为"尾索引"
    // 即counte[num] - 1是num在res中最后一次出现的索引
    for (int i = 0;i < counter.size() - 1;i++) {
        counter[i + 1] += counter[i];
    }
    // 4、倒序遍历nums，将各元素填入结果数组res
    std::vector<int> res(nums.size(),0);
    for (int i = nums.size() - 1;i >= 0;i--) {
        int num = nums[i];
        // 将num放置到对应索引处
        res[counter[num] - 1] = num;
        // 令前缀和自减1，得到下次放置num的索引
        counter[num]--;
    }
    // 使用结果数组res覆盖原数组nums
    nums = res;
}

void SORTING::countingSortDigit(std::vector<int> &nums,int exp) {
    // 十进制的位范围为0~9，因此需要长度为10的桶
    std::vector<int> counter(10,0);
    int n = nums.size();
    // 统计0~9各数字的出现次数
    for (int i = 0;i < n;i++) {
        int d = digit(nums[i],exp); // 获取nums[i]第k位，记为d
        counter[d]++;
    }
    // 求前缀和，将“出现个数”转换为“数组索引”
    for (int i = 1;i < 10;i++) {
        counter[i] += counter[i - 1];
    }

    // 倒序遍历，根据桶内统计结果，将各元素填入res
    std::vector<int> res(n, 0);
    for (int i = n - 1;i >= 0;i--) {
        int d = digit(nums[i],exp);
        int j = counter[d] - 1;  // 获取d在数组中的索引j
        res[j] = nums[i];   //  将当前元素填入索引j
        counter[d]--;       // 将d的数量减1
    }

    // 使用结果覆盖原数组nums
    for (int i = 0;i < n;i++) {
        nums[i] = res[i];
    }
}

void SORTING::radixSort(std::vector<int> &nums) {
    std::cout << "基数排序"  << std::endl;
    // 获取数组的最大元素，用于判断最大位数
    int m = *max_element(nums.begin(),nums.end());
    
    // 按照从低位到高位的顺序遍历
    for (int exp = 1;exp <= m;exp *= 10) {
        // 对数组元素的第k位执行计数排序
        // k = 1 -> exp = 1
        // k = 2 -> exp = 2
        // 即 exp = 10^(k-1)
        countingSortDigit(nums,exp);
    }
}